package com.egg.color;

import java.util.Arrays;

public class GraphColor {
	private int[][] graph;
	private int[] colors;
	private int[] result;

	public GraphColor() {
		graph = new int[][] { { 1, 1, 0, 0, 0, 1 }, { 1, 1, 1, 0, 1, 0 },
				{ 0, 1, 1, 1, 0, 0 }, { 0, 0, 1, 1, 0, 1 },
				{ 0, 1, 0, 0, 1, 0 }, { 1, 0, 0, 1, 0, 1 } };
		result = new int[graph.length];
		colors = new int[] { 1, 2, 3, 4 };
	}

	public boolean color() {
		return colorProcess(0);
	}
	
	private boolean colorProcess(int index) {
		if (index >= graph.length) {
			return true;
		}

		for (int c : colors) {
			result[index] = c;

			if (isValid(index)) {
				boolean flag = colorProcess(index + 1);
				if (flag) {
					return true;
				}
			}
		}
		return false;
	}

	private boolean isValid(int index) {
		for (int i = 0; i < graph[index].length; i++) {
			if (i != index && graph[index][i] == 1
					&& result[i] == result[index]) {
				return false;
			}
		}
		return true;
	}

	public int[] getResult() {
		return Arrays.copyOf(result, result.length);
	}

	public static void main(String[] args) {
		GraphColor gc = new GraphColor();
		gc.color();

		System.out.print("[ ");
		for (int i : gc.getResult()) {
			System.out.print(i + " ");
		}
		System.out.println("]");
	}
}
